Data Structure
Q72.
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(n^{a}log^{b}n+m^{c}log^{d}n), the value of a + 10b + 100c + 1000d is _______.Q73.
The number of rotations required to insert a sequence of elements 9, 6, 5, 8, 7, 10 into an empty AVL tree is?Q74.
The worst case running time to search for an element in a balanced binary search tree with n2^{n} elements isQ75.
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.Q76.
A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then the worst-case time complexity of the program isQ78.
In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node g?Q79.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: A 2-3 tree is such that a. All internal nodes have either 2 or 3 children b. All paths from root to the leaves have the same length.The number of internal nodes of a 2-3 tree having 9 leaves could be